package com.samxcode.leetcode;

/**
 * Given an array of non-negative integers, you are initially positioned at the first index of the
 * array.
 * 
 * Each element in the array represents your maximum jump length at that position.
 * 
 * Your goal is to reach the last index in the minimum number of jumps.
 * 
 * For example: Given array A = [2,3,1,1,4]
 * 
 * The minimum number of jumps to reach the last index is 2. (Jump 1 step from index 0 to 1, then 3
 * steps to the last index.)
 * 
 * Solution: 
 * 贪心法 在能够到达的范围之内，选择一个能够到达最远距离的点，更新步数，和更新最远到达的范围。
 * DP 记录上一步所能达到的最远位置，移动下标i，如果i超过上一步最远位置则更新步数+1
 * 
 * @author Sam
 *
 */
public class JumpGame2 {
    
    public static void main(String[] args) {
        int[] nums = {2, 3, 0, 1, 4};
        System.out.println(jumpDP(nums));
    }

    public static int jump(int[] nums) {
        int max = 0, res = 0, end = 0;
        for (int i = 0; i <= nums.length;) {
            if (max >= nums.length - 1) {
                return res;
            }
            end = max;
            for (; i <= end; i++) {
                max = Math.max(max, i + nums[i]);
            }
            res++;
        }
        return res;
    }
    
    
    public static int jumpDP(int[] nums) {
        int lastReach = 0, res = 0, max = 0;
        for (int i = 0; i < nums.length; i++) {
            if (i > lastReach) {
                res++;
                lastReach = max;
            }
            max = Math.max(max, i + nums[i]);
        }
        return res;
    }
}
